.NH
Interpreter
.PP
In this section, we will discuss
the execution of Tokio programs in more detail.
At the end of this chapter we will see an experimental
description of unify processor (UP) for the parallel inference engine PIE.
UP executes unification of Prolog by hardware, and its experimental system
is presently being constructed [14].
.NH 2
Temporal variable and reduction to the future
.PP
Tokio has two different kinds of unifiers.
One is an unifier only for the current state.
The other is an unifier for all remaining times.
.IP
.nf
inc(A) :- #(@A=A+1).   (34)
?- length(3),A=1,inc(A),#write(A).
1234
.fi
.LP
If we use this statement,
it is obvious that the variable in the head of Tokio
clause has to be unified in all remaining times.
In the head of the 'inc' clause,
all the values of A, i.e. 1,2,3 and 4 are unified.
On the other hand, 'A=1' means
unification only in the current time.
.PP
Our interpreter first reduces all intervals beginning
with 0, i.e., <0,fin>.
In this process other intervals may be generated, and the
interpreter reduces these intervals in the order of the beginning time.
Always '#', next '@' and chop '&&' generate intervals and the reduction of
these operators is called 'reduction to the future'.
.NH
ITL operator -- fin,keep
.PP
To execute 'fin' and 'keep' we have to know whether the
interval is terminated or not.
However the ending time of the interval can be determined
only after all predicates in that
interval are reduced.
Our solution is a simple one.
First we reduce all
predicates except 'fin' and 'keep', then we execute 'fin' or 'keep'
alternatively depending on whether the interval
is terminated or not.
However, this leads to some odd behaviors.
.IP
.nf
?-fin(A=1),#write(A),length(0).
_0
yes
.fi
.LP
In the above example, #write(A) is executed before fin(A=1) is executed.
Underlined printout means unassigned value, also the above execution
is not correct ('1' should be printed out.).
Generally speaking, the order of
the execution in the same time is uncertain.
If a temporal operator is not used, however,
then the order of the execution is the same as that of Prolog.
.NH 2
Finite interval
.PP
Consider the statement 'true', which means there is nothing to be
evaluated.
It has no length specifier such that 'halt' or 'length'.
This statement can have arbitrary length.
In such cases,
the execution of this interval is made as short as possible in our
interpreter.
When all the executions have terminated
except those of 'fin' and 'keep', if there is no length specifier, the
interval is cut off at the next time, that is, the
ending time of this interval is now+1.
In this process, an empty interval is not generated.
If the reducing process is failed later,
the interval cut off is cleared,
that is, interval length is incremented, just as in Prolog's backtracking.
.IP examples
.nf
.in 4
?-A=0,A gets A+1,#write(A).
01
A=0 ;
12
A=0 ;
23
yes
.fi
.LP
\';' is a request for an alternative solution [10].
In the first attempt, the interpreter tries to reduce the whole clause at
length(1).
Then typing ';' causes backtracking a unit of time, and extend
the interval by one unit of time.
The resulting interval length is 2.
In this case, each backtrack makes the interval one unit longer.
.NH 2
Global Variable and Static Variable
.PP
Figure (14) is a description of memory system in Tokio.
The contents of memory are represented with a  list structure.
In this program, variables Contents,
Cmd, Data, Adr exist throughout the calculation.
Full description of such variables is somewhat tedious.
For readability of descriptions, we can use global variables.
The operator '*' creates a global variable from an atom.
It requires declaration for efficiency of execution.
Global variables can be used as logical
variables and can appear in different clauses.
Their scope is static.
Figure (15) is the same memory system using global variables.
.PP
In large systems, many memories are used, and if we write a memory
like the one in the above example, though it is a detailed description,
it is not readable.
Tokio's static variable is a reduced notation for such a complicated memory.
Static variables have the same values as the past ones until they are
explicitly changed.
So they behave just like storage.
Their syntax is the same as that of global variables,
only declaration is different.
References to static variables are the same as global,
but assignment demands a special form.
.IP examples
*s := 1.
.LP
This is an instantaneous assignment.
The value of *s in the current time is set to 1,
and this value is stable until the next assignment.
.IP
*s <= 1.
.PP
This form of assignment is a temporal assignment.
The effect of assignment 
appears at the end of the interval.
The first assignment is used as individual latch.
That latch can be read immediately by others.
The second assingment is used as common bus memory.
The memory unit is considered a remote device.
The effect of assignment is delayed in some interval.
It is an error to assign two different values to the same variable
at the same time.
.NH 2
Examples of the Unify Processor
.PP
Figure (16) is a description of the  Unify Processor (UP) [14] in Tokio.
UP has two structure of clause, one for definition, the other for goals.
This unification algorithm is executed in the following way.
Each execution corresponds to one Tokio clause.
.IP loop_unif 20
First the length of goal clause  is pick up.
If length is 0 then unification succeeds.
Otherwise the next element is picked up.
.IP fetch_unif
If these elements are variables,
the references to these are resolved repeatedly.
.IP fetch_unif2
Final part consists of five cases.
.RS
.IP 1)
Goal and definition are both variables.
.IP 2)
Goal is a variable but definition is not.
.IP 3)
Goal is defined but definition is a variable.
In these three cases, appropriate assignments occur.
.IP 4)
Goal and definition are both lists.
In this case, UP's current statuses are pushed into stacks, then
unification is executed recursively.
These stacks are popped at the end of
each recursive unification.
.IP 5)
If the above four cases do not occur, the
goal and definition have to be the same element.
Otherwise unification fails.
.RE
.LP
In this program, state transition is described as a predicate call.
These predicates are considered to be interval names,
and their call corresponds to 'goto' statement
between the intervals.
.PP
There are several kinds of new operators.
The first three clauses are function definitions.
It selects an element from structure (Data,Tag,Map).
This structure is UP's tag structure and it is an address of UP's
internal memory.
UP has two memory planes for definition clause and goal clause.
Element Map indicates which
memory plane is used with 'd' or 'g'. 'case2' is a case statement that
is used only in the predicate 'fetch_unif2'.
\'global' and 'static' predicates declare
static and global variables. 'memory(_)',
'stack_ln(_)', 'stack_ga(_)'
and 'stack_da(_)' are array of static variables.
.PP
The basic execution is as follows.
\'test' is a main clause of this program.
It initiates memories that
contain definitions of 'append' and 'goal'.
In memory structure there are five
tags, INT, ATOM, LIST, VAR and UNDEF.
The first element of the clause is its length.
In the next interval, predicate 'init' is executed. 
It first reads data, and then it sets the running flag '*run',
and then falls into 'loop_unif'.
.PP
In 'loop_unif' the length of data is checked. If it is 0, then
stack depth is checked.
If the stack is empty, then the unification succeeds.
Otherwise stacks are popped and the execution continues.
The Next interval is a fetch cycle.
Variable references to goal and definition are resolved in this stage.
In fetch cycle, goal memory and definition memory may be in conflict.
To avoid these conflicts flags g_bus and d_bus are checked
in the predicate 'fetch_unif2'.
This includes a case statement of the above five case.
.NH 2
Current implementation
.PP
The Tokio interpreter is coded in C-Prolog,
which is developed at Edingburgh University, and runs on VAX11 series
computers under UNIX.
It has 316 clauses.
Currently the execution speed is very slow because of that of Prolog.
It takes about 94 seconds (VAX11/780 CPUTIME) to simulate the 'append'
program using the description for UP of figure (16).
We have also written a compiler
which translate Tokio programs into Prolog program and
is 5 times faster than the interpreter in C-Prolog.
This compiler's object code is 7 times slower than the original Prolog
for a Prolog program.
The compiler is written in Prolog and it has 467 clauses.
However, we are now developing an interpreter and a compiler using the C
language on VAX and main frame computers.
The execution speed is expected to be 50 to 100 times faster.
Tokio includes Prolog, so Prolog is also executed very fast.
